// 279. 完全平方数

function numSquares(n: number): number {
    const result: number[] = new Array(n + 1).fill(0);

    for (let i = 1; i < n + 1; i++) {
        // 最坏的情况1+1+1累加
        result[i] = i
        // 减去平方数 1，4，9...
        // 每次循环去寻找减去平方之后最少的那次 +1就是最少的
        for (let j = 1; j * j <= i; j++) {
            result[i] = Math.min(result[i], result[i - j * j] + 1);
        }
    }
    // console.log(result)
    return result[n]
};

console.log(numSquares(11))